Birthday Problem

Birthday Problem: k명 중에 2명 이상이 같은 생일을 가질 확률은 어떻게 되는가?

Assumption:

Problem: $k$ 가 몇 명 이상이어야 같은 생일을 가진 사람들이 있을 확률이 50%일까?

$k > 365$ : 확률은 1이 된다. (pigeon hole principle: 생일은 365일내에 존재하므로, 365명보다 사람이 많으면 반드시 생일이 겹치게 될 것임.)
$k \leq 365$ 라 할 때, 여사건의 확률을 먼저 naive-Probability를 이용해 계산 가능하다. 생일이 겹치지 않을 확률을 먼저 계산하여, $P (At least one shared) = 1 - P (no match)$ 를 이용해 계산 가능하다. (Complement Rule)
1. 일별 출생 확률이 동일하다고 가정했으므로 분모는 곱의 법칙에 의해 $36 5^{k}$ 가 된다.
2. 분자는 순서 있는 비복원 Counting(=순열)과 동일해진다. 즉, 첫 사람의 생일이 결정되면 그 다음 사람은 그 생일 만을 제외하고 남은 364개의 생일 중 하나를 가진다.

P (no match) = \frac{365 \times 364 \times ... \times ( 365 - k + 1 )}{36 5 ^{k}}

Number of People (K)	Probability of at Least One Shared Birthday
10	11.7%
20	41.1%
23	50.7%
30	70.6%
40	89.1%
50	97.0%
100	99.999%

$k = 23$ 일 때, $P (match) = 50.7%$ 정도로 $50%$ 과 비슷해진다.

Why Counterintuitive?

위 문제는 365명에 비해 23명 만으로도 생일이 겹칠 확률이 50%에 근접해진다는 것이 비직관적으로 느껴진다.

이는 $K$ 개의 사람 중 2개를 조합해 짝을 만드는 방법의 수를 따져보면 직관적이게 된다.

Pairs = (2 K) = \frac{K ( K - 1 )}{2}

위 공식에 $K = 23$ 을 넣으면, 그 수는 253이 되므로 생일이 일치할 확률은 253번의 기회나 존재한다.

푸아송 분포로 근사시키면 더 간단하게도 계산 가능하다.

$Pairs = (2 K) = \frac{K ( K - 1 )}{2} = N$ 라고 하면, 이는 총 시도의 횟수. 즉 서로 생일이 같은 짝을 찾는 모든 가능한 시도의 횟수라 할 수 있다.
한 쌍에서, 한 명의 생일이 이미 정해지면 다른 사람의 생일도 일치할 확률은 $p = \frac{1}{365}$

이 때, 서로 생일이 같은 쌍의 개수를 $X$ 라 하면 이는 푸아송 분포와 근사하게 볼 수 있다. 이를 위해 parameter $λ$ 를 찾으면,

λ = E [X] = N \times p = \frac{K ( K - 1 )}{730}

그리고, 최소한 그러한 쌍을 하나라도 찾아야 하므로 그럴 확률은

P (X \geq 1) = 1 - P (X = 0) \approx 1 - \frac{e ^{- λ} λ ^{0}}{0 !} = 1 - e^{- λ} = 1 - e^{\frac{K ( K - 1 )}{730}}

위에 식에 대해서 $k = 23$ 을 적용하면, 그 확률은 약 $50$ %가 된다.

import numpy as np

def poisson(x):
    a = x*(x-1)
    a = a / 730
    return 1- np.exp(-a)
    

print(poisson(int(input())))

0.5000017521827107

만약 쌍이 아닌 3개로 이루어진 쌍을 찾는 경우에도 동일하게 근사하여 편하게 계산 가능하다.